package leetcode_1_200;

import java.util.*;

public class LeeCode_187 {
    public static void main(String[] args) {
        System.out.println(findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"));
        System.out.println(findRepeatedDnaSequences("AAAAAAAAAAA"));
    }
    private static List<String> findRepeatedDnaSequences2(String s) {
       int n = s.length();
       List<String> ans = new ArrayList<>();
        if (n < 10)
            return ans;
        int l = 0, r = 9;
        Set<String> set = new HashSet<>();
        while (r < n){
            String son = s.substring(l, r + 1);
            if (set.contains(son) && !ans.contains(son)){
                ans.add(son);
            }else {
                set.add(son);
            }
            l++;
            r++;
        }
        return ans;
    }
    private static List<String> findRepeatedDnaSequences(String s) {
        List<String> ans = new ArrayList<>();
        if (s.length() < 10){
            return ans;
        }
        String[] ss = new String[s.length() - 9];
        int r = 10;
        int index = 1;
        StringBuilder sb = new StringBuilder();
        sb.append(s, 0, 10);
        ss[0] = sb.toString();
        while (r < s.length()){
            sb.deleteCharAt(0);
            sb.append(s.charAt(r));
            ss[index] = sb.toString();
            r++;
            index++;
        }
        Arrays.sort(ss, (o1, o2) -> {
            for (int i = 0; i < o1.length(); i++) {
                if (o1.charAt(i) == o2.charAt(i)){
                    continue;
                }
                return o1.charAt(i) - o2.charAt(i);
            }
            return 1;
        });
        for (int i = 0; i < ss.length - 1; i++) {
            if (ss[i].equals(ss[i + 1])){
                ans.add(ss[i]);
                while (i + 1 < ss.length && ss[i].equals(ss[i + 1])){
                    i++;
                }
            }
        }
        return ans;
    }
}
